<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
   "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/>
<head>
    <title>binaryheap</title>
    <link rel="stylesheet" href="ldoc.css" type="text/css" />
</head>
<body>

<div id="container">

<div id="product">
	<div id="product_logo"></div>
	<div id="product_name"><big><b></b></big></div>
	<div id="product_description"></div>
</div> <!-- id="product" -->


<div id="main">


<!-- Menu -->

<div id="navigation">
<br/>
<h1>binaryheap.lua</h1>


<h2>Contents</h2>
<ul>
<li><a href="#Basic_heap">Basic heap </a></li>
<li><a href="#Plain_heap">Plain heap </a></li>
<li><a href="#Unique_heap">Unique heap </a></li>
</ul>


<h2>Modules</h2>
<ul class="nowrap">
  <li><strong>binaryheap</strong></li>
</ul>
<h2>Topics</h2>
<ul class="">
  <li><a href="topics/readme.md.html">readme</a></li>
</ul>

</div>

<div id="content">

<h1>Module <code>binaryheap</code></h1>
<p>Binary heap implementation</p>

<p> A binary heap (or binary tree) is a <a href="http://en.wikipedia.org/wiki/Binary_heap">sorting algorithm</a>.</p>
<p>


<p> The 'plain binary heap' is managed by positions. Which are hard to get once
 an element is inserted. It can be anywhere in the list because it is re-sorted
 upon insertion/deletion of items. The array with values is stored in field
 <code>values</code>:</p>


<pre>
<span class="backtick"><code>peek = heap.values[1]</code></span>
</pre>

<p> A 'unique binary heap' is where the payload is unique and the payload itself
 also stored (as key) in the heap with the position as value, as in;</p>

<pre>
<span class="backtick"><code>heap.reverse[payload] = [pos]</code></span>
</pre>

<p> Due to this setup the reverse search, based on payload, is now a
 much faster operation because instead of traversing the list/heap,
 you can do;</p>

<pre>
<span class="backtick"><code>pos = heap.reverse[payload]</code></span>
</pre>

<p> This means that deleting elements from a 'unique binary heap' is
 faster than from a plain heap.</p>

<p> All management functions in the 'unique binary heap' take <code>payload</code>
 instead of <code>pos</code> as argument.
 Note that the value of the payload must be unique!</p>

<p> Fields of heap object:</p>

<ul>
    <li>values - array of values</li>
    <li>payloads - array of payloads (unique binary heap only)</li>
    <li>reverse - map from payloads to indices (unique binary heap only)</li>
</ul>
</p>


<h2><a href="#Basic_heap">Basic heap </a></h2>
<table class="function_list">
	<tr>
	<td class="name" nowrap><a href="#binaryHeap">binaryHeap (swap, erase, lt)</a></td>
	<td class="summary">Creates a new binary heap.</td>
	</tr>
</table>
<h2><a href="#Plain_heap">Plain heap </a></h2>
<table class="function_list">
	<tr>
	<td class="name" nowrap><a href="#heap:insert">heap:insert (value)</a></td>
	<td class="summary">Inserts an element in the heap.</td>
	</tr>
	<tr>
	<td class="name" nowrap><a href="#heap:peek">heap:peek ()</a></td>
	<td class="summary">Returns the element at the top of the heap, without removing it.</td>
	</tr>
	<tr>
	<td class="name" nowrap><a href="#heap:pop">heap:pop ()</a></td>
	<td class="summary">Removes the top of the heap and returns it.</td>
	</tr>
	<tr>
	<td class="name" nowrap><a href="#heap:remove">heap:remove (pos)</a></td>
	<td class="summary">Removes an element from the heap.</td>
	</tr>
	<tr>
	<td class="name" nowrap><a href="#heap:size">heap:size ()</a></td>
	<td class="summary">Returns the number of elements in the heap.</td>
	</tr>
	<tr>
	<td class="name" nowrap><a href="#heap:update">heap:update (pos, newValue)</a></td>
	<td class="summary">Updates the value of an element in the heap.</td>
	</tr>
	<tr>
	<td class="name" nowrap><a href="#maxHeap">maxHeap (gt)</a></td>
	<td class="summary">Creates a new max-heap, where the largest value is at the top.</td>
	</tr>
	<tr>
	<td class="name" nowrap><a href="#minHeap">minHeap (lt)</a></td>
	<td class="summary">Creates a new min-heap, where the smallest value is at the top.</td>
	</tr>
</table>
<h2><a href="#Unique_heap">Unique heap </a></h2>
<table class="function_list">
	<tr>
	<td class="name" nowrap><a href="#heap:size">heap:size ()</a></td>
	<td class="summary">Returns the number of elements in the heap.</td>
	</tr>
	<tr>
	<td class="name" nowrap><a href="#maxUnique">maxUnique (gt)</a></td>
	<td class="summary">Creates a new max-heap with unique payloads.</td>
	</tr>
	<tr>
	<td class="name" nowrap><a href="#minUnique">minUnique (lt)</a></td>
	<td class="summary">Creates a new min-heap with unique payloads.</td>
	</tr>
	<tr>
	<td class="name" nowrap><a href="#unique:insert">unique:insert (value, payload)</a></td>
	<td class="summary">Inserts an element in the heap.</td>
	</tr>
	<tr>
	<td class="name" nowrap><a href="#unique:peek">unique:peek ()</a></td>
	<td class="summary">Returns the element at the top of the heap, without removing it.</td>
	</tr>
	<tr>
	<td class="name" nowrap><a href="#unique:peekValue">unique:peekValue ()</a></td>
	<td class="summary">Returns the element at the top of the heap, without removing it.</td>
	</tr>
	<tr>
	<td class="name" nowrap><a href="#unique:pop">unique:pop ()</a></td>
	<td class="summary">Removes the top of the heap and returns it.</td>
	</tr>
	<tr>
	<td class="name" nowrap><a href="#unique:remove">unique:remove (payload)</a></td>
	<td class="summary">Removes an element from the heap.</td>
	</tr>
	<tr>
	<td class="name" nowrap><a href="#unique:update">unique:update (payload, newValue)</a></td>
	<td class="summary">Updates the value of an element in the heap.</td>
	</tr>
	<tr>
	<td class="name" nowrap><a href="#unique:valueByPayload">unique:valueByPayload (payload)</a></td>
	<td class="summary">Returns the value associated with the payload</td>
	</tr>
</table>

<br/>
<br/>


    <h2 class="section-header has-description"><a name="Basic_heap"></a>Basic heap </h2>

          <div class="section-description">
           This is the base implementation of the heap. Under regular circumstances
 this should not be used, instead use a <em>Plain heap</em> or <em>Unique heap</em>.
          </div>
    <dl class="function">
    <dt>
    <a name = "binaryHeap"></a>
    <strong>binaryHeap (swap, erase, lt)</strong>
    </dt>
    <dd>
    Creates a new binary heap.
 This is the core of all heaps, the others
 are built upon these sorting functions.


    <h3>Parameters:</h3>
    <ul>
        <li><span class="parameter">swap</span>
         (function) <code>swap(heap, idx1, idx2)</code> swaps values at
 <code>idx1</code> and <code>idx2</code> in the heaps <code>heap.values</code> and <code>heap.payloads</code> lists (see
 return value below).
        </li>
        <li><span class="parameter">erase</span>
         (function) <code>swap(heap, position)</code> raw removal
        </li>
        <li><span class="parameter">lt</span>
         (function) in <code>lt(a, b)</code> returns <code>true</code> when <code>a &lt; b</code> (for a min-heap)
        </li>
    </ul>

    <h3>Returns:</h3>
    <ol>

         table with two methods; <code>heap:bubbleUp(pos)</code> and <code>heap:sinkDown(pos)</code>
 that implement the sorting algorithm and two fields; <code>heap.values</code> and
 <code>heap.payloads</code> being lists, holding the values and payloads respectively.
    </ol>




</dd>
</dl>
    <h2 class="section-header has-description"><a name="Plain_heap"></a>Plain heap </h2>

          <div class="section-description">
           A plain heap carries a single piece of information per entry. This can be
 any type (except <code>nil</code>), as long as the comparison function used to create
 the heap can handle it.
          </div>
    <dl class="function">
    <dt>
    <a name = "heap:insert"></a>
    <strong>heap:insert (value)</strong>
    </dt>
    <dd>
    Inserts an element in the heap.


    <h3>Parameters:</h3>
    <ul>
        <li><span class="parameter">value</span>
         the value used for sorting this element
        </li>
    </ul>

    <h3>Returns:</h3>
    <ol>

        nothing, or throws an error on bad input
    </ol>




</dd>
    <dt>
    <a name = "heap:peek"></a>
    <strong>heap:peek ()</strong>
    </dt>
    <dd>
    Returns the element at the top of the heap, without removing it.



    <h3>Returns:</h3>
    <ol>

        value at the top, or <code>nil</code> if there is none
    </ol>




</dd>
    <dt>
    <a name = "heap:pop"></a>
    <strong>heap:pop ()</strong>
    </dt>
    <dd>
    Removes the top of the heap and returns it.



    <h3>Returns:</h3>
    <ol>

        value at the top, or <code>nil</code> if there is none
    </ol>




</dd>
    <dt>
    <a name = "heap:remove"></a>
    <strong>heap:remove (pos)</strong>
    </dt>
    <dd>
    Removes an element from the heap.


    <h3>Parameters:</h3>
    <ul>
        <li><span class="parameter">pos</span>
         the position to remove
        </li>
    </ul>

    <h3>Returns:</h3>
    <ol>

        value, or nil if a bad <code>pos</code> value was provided
    </ol>




</dd>
    <dt>
    <a name = "heap:size"></a>
    <strong>heap:size ()</strong>
    </dt>
    <dd>
    Returns the number of elements in the heap.



    <h3>Returns:</h3>
    <ol>

        number of elements
    </ol>




</dd>
    <dt>
    <a name = "heap:update"></a>
    <strong>heap:update (pos, newValue)</strong>
    </dt>
    <dd>
    Updates the value of an element in the heap.


    <h3>Parameters:</h3>
    <ul>
        <li><span class="parameter">pos</span>
         the position which value to update
        </li>
        <li><span class="parameter">newValue</span>
         the new value to use for this payload
        </li>
    </ul>





</dd>
    <dt>
    <a name = "maxHeap"></a>
    <strong>maxHeap (gt)</strong>
    </dt>
    <dd>
    Creates a new max-heap, where the largest value is at the top.


    <h3>Parameters:</h3>
    <ul>
        <li><span class="parameter">gt</span>
         (optional) comparison function (greater-than), see <a href="index.html#binaryHeap">binaryHeap</a>.
        </li>
    </ul>

    <h3>Returns:</h3>
    <ol>

        the new heap
    </ol>




</dd>
    <dt>
    <a name = "minHeap"></a>
    <strong>minHeap (lt)</strong>
    </dt>
    <dd>
    Creates a new min-heap, where the smallest value is at the top.


    <h3>Parameters:</h3>
    <ul>
        <li><span class="parameter">lt</span>
         (optional) comparison function (less-than), see <a href="index.html#binaryHeap">binaryHeap</a>.
        </li>
    </ul>

    <h3>Returns:</h3>
    <ol>

        the new heap
    </ol>




</dd>
</dl>
    <h2 class="section-header has-description"><a name="Unique_heap"></a>Unique heap </h2>

          <div class="section-description">
           A unique heap carries 2 pieces of information per entry.</p>

<ol>
    <li>The <code>value</code>, this is used for ordering the heap. It can be any type (except
    <code>nil</code>), as long as the comparison function used to create the heap can
    handle it.</li>
    <li>The <code>payload</code>, this can be any type (except <code>nil</code>), but it MUST be unique.</li>
</ol>

<p> With the 'unique heap' it is easier to remove elements from the heap.
          </div>
    <dl class="function">
    <dt>
    <a name = "heap:size"></a>
    <strong>heap:size ()</strong>
    </dt>
    <dd>
    Returns the number of elements in the heap.



    <h3>Returns:</h3>
    <ol>

        number of elements
    </ol>




</dd>
    <dt>
    <a name = "maxUnique"></a>
    <strong>maxUnique (gt)</strong>
    </dt>
    <dd>
    Creates a new max-heap with unique payloads.
 A max-heap is where the largest value is at the top.</p>

<p> <em>NOTE</em>: All management functions in the 'unique binary heap'
 take <code>payload</code> instead of <code>pos</code> as argument.


    <h3>Parameters:</h3>
    <ul>
        <li><span class="parameter">gt</span>
         (optional) comparison function (greater-than), see <a href="index.html#binaryHeap">binaryHeap</a>.
        </li>
    </ul>

    <h3>Returns:</h3>
    <ol>

        the new heap
    </ol>




</dd>
    <dt>
    <a name = "minUnique"></a>
    <strong>minUnique (lt)</strong>
    </dt>
    <dd>
    Creates a new min-heap with unique payloads.
 A min-heap is where the smallest value is at the top.</p>

<p> <em>NOTE</em>: All management functions in the 'unique binary heap'
 take <code>payload</code> instead of <code>pos</code> as argument.


    <h3>Parameters:</h3>
    <ul>
        <li><span class="parameter">lt</span>
         (optional) comparison function (less-than), see <a href="index.html#binaryHeap">binaryHeap</a>.
        </li>
    </ul>

    <h3>Returns:</h3>
    <ol>

        the new heap
    </ol>




</dd>
    <dt>
    <a name = "unique:insert"></a>
    <strong>unique:insert (value, payload)</strong>
    </dt>
    <dd>
    Inserts an element in the heap.


    <h3>Parameters:</h3>
    <ul>
        <li><span class="parameter">value</span>
         the value used for sorting this element
        </li>
        <li><span class="parameter">payload</span>
         the payload attached to this element
        </li>
    </ul>

    <h3>Returns:</h3>
    <ol>

        nothing, or throws an error on bad input
    </ol>




</dd>
    <dt>
    <a name = "unique:peek"></a>
    <strong>unique:peek ()</strong>
    </dt>
    <dd>
    Returns the element at the top of the heap, without removing it.



    <h3>Returns:</h3>
    <ol>

        payload, value, or <code>nil</code> if there is none
    </ol>




</dd>
    <dt>
    <a name = "unique:peekValue"></a>
    <strong>unique:peekValue ()</strong>
    </dt>
    <dd>
    Returns the element at the top of the heap, without removing it.



    <h3>Returns:</h3>
    <ol>

        value at the top, or <code>nil</code> if there is none
    </ol>



    <h3>Usage:</h3>
    <ul>
        <pre class="example"><span class="comment">-- simple timer based heap example
</span><span class="keyword">while</span> <span class="keyword">true</span> <span class="keyword">do</span>
  sleep(heap:peekValue() - gettime())  <span class="comment">-- assume LuaSocket gettime function
</span>  <span class="global">coroutine</span>.resume((heap:pop()))       <span class="comment">-- assumes payload to be a coroutine,
</span>                                       <span class="comment">-- double parens to drop extra return value
</span><span class="keyword">end</span></pre>
    </ul>

</dd>
    <dt>
    <a name = "unique:pop"></a>
    <strong>unique:pop ()</strong>
    </dt>
    <dd>
    Removes the top of the heap and returns it.
 When used with timers, <a href="index.html#unique:pop">pop</a> will return the payload that is due.</p>

<p> Note: this function returns <code>payload</code> as the first result to prevent
 extra locals when retrieving the <code>payload</code>.



    <h3>Returns:</h3>
    <ol>

        payload, value, or <code>nil</code> if there is none
    </ol>




</dd>
    <dt>
    <a name = "unique:remove"></a>
    <strong>unique:remove (payload)</strong>
    </dt>
    <dd>
    Removes an element from the heap.


    <h3>Parameters:</h3>
    <ul>
        <li><span class="parameter">payload</span>
         the payload to remove
        </li>
    </ul>

    <h3>Returns:</h3>
    <ol>

        value, payload or nil if not found
    </ol>




</dd>
    <dt>
    <a name = "unique:update"></a>
    <strong>unique:update (payload, newValue)</strong>
    </dt>
    <dd>
    Updates the value of an element in the heap.


    <h3>Parameters:</h3>
    <ul>
        <li><span class="parameter">payload</span>
         the payoad whose value to update
        </li>
        <li><span class="parameter">newValue</span>
         the new value to use for this payload
        </li>
    </ul>

    <h3>Returns:</h3>
    <ol>

        nothing, or throws an error on bad input
    </ol>




</dd>
    <dt>
    <a name = "unique:valueByPayload"></a>
    <strong>unique:valueByPayload (payload)</strong>
    </dt>
    <dd>
    Returns the value associated with the payload


    <h3>Parameters:</h3>
    <ul>
        <li><span class="parameter">payload</span>
         the payload to lookup
        </li>
    </ul>

    <h3>Returns:</h3>
    <ol>

        value or nil if no such payload exists
    </ol>




</dd>
</dl>


</div> <!-- id="content" -->
</div> <!-- id="main" -->
<div id="about">
<i>generated by <a href="http://github.com/stevedonovan/LDoc">LDoc 1.4.6</a></i>
<i style="float:right;">Last updated 2018-11-07 17:56:33 </i>
</div> <!-- id="about" -->
</div> <!-- id="container" -->
</body>
</html>
